/* 动态规划求解硬币问题
* 使用指定的几种硬币，每种硬币不限个数，组合得到指定面额，求所需硬币个数最少的组合 */

#include<list>
#include<algorithm>
#include<iostream>
using namespace std;

int main(void)
{
	constexpr int N = 6;
	int coins[N] = { 1, 2, 7, 8, 12, 50 };
	constexpr int MAXC = 50;

	list<int> listCoins[MAXC + 1];
	int coinNumbers[MAXC + 1];

	for (int i = 0; i <= MAXC; i++)
	{
		coinNumbers[i] = i / coins[0];
		listCoins[i].assign(coinNumbers[i], 1);
	}

	for (int i = 1; i < N; i++)
	{
		for (int n = 1; n <= MAXC; n++)
		{
			int leftCoins = n - coins[i];

			if (leftCoins >= 0)
			{
				int newCount = coinNumbers[leftCoins] + 1;
				if (newCount < coinNumbers[n])
				{
					coinNumbers[n] = newCount;
					listCoins[n].assign(listCoins[leftCoins].begin(), listCoins[leftCoins].end());
					listCoins[n].push_back(coins[i]);
				}
			}
		}
	}

	for (int i = 1; i <= MAXC; i++)
	{
		cout << i << " need at least " << coinNumbers[i] << " coins, : ";
		for_each(listCoins[i].begin(), listCoins[i].end(), [](int e) {cout << e << " "; });
		cout << "\n";
	}

	return 0;
}
